#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    ListNode* _merge(ListNode* head1, ListNode* head2)
    {
        ListNode* dummyNode, * cur;
        dummyNode = cur = new ListNode(-1);
        while (head1 != nullptr && head2 != nullptr)
        {
            if (head1->val < head2->val)
            {
                cur->next = head1;
                head1 = head1->next;
            }
            else
            {
                cur->next = head2;
                head2 = head2->next;
            }
            cur = cur->next;
        }
        if (head1)
        {
            cur->next = head1;
        }
        if (head2)
        {
            cur->next = head2;
        }
        ListNode* head = dummyNode->next;
        delete dummyNode;
        return head;
    }
    ListNode* sortList(ListNode* head)
    {
        if (head == nullptr)
            return head;
        int len = 0;
        ListNode* curlen = head;
        for (; curlen != nullptr; curlen = curlen->next, len++);

        ListNode* dummyNode = new ListNode(-1);
        dummyNode->next = head;
        for (int i = 1; i < len; i <<= 1)
        {
            ListNode* cur = dummyNode->next;
            ListNode* prev = dummyNode;
            while (cur != nullptr)
            {
                ListNode* head1 = cur;
                for (int j = 1; j < i && cur->next != nullptr; ++j)
                {
                    cur = cur->next;
                }
                ListNode* head2 = cur->next;
                cur->next = nullptr;
                cur = head2;
                for (int j = 1; j < i && cur != nullptr && cur->next != nullptr; ++j)
                {
                    cur = cur->next;
                }
                ListNode* Next = nullptr;
                if (cur != nullptr)
                {
                    Next = cur->next;
                    cur->next = nullptr;
                }
                prev->next = _merge(head1, head2);
                while (prev->next != nullptr)
                {
                    prev = prev->next;
                }
                cur = Next;
            }
        }
        head = dummyNode->next;
        delete dummyNode;
        return head;
    }
};

